package main

import "fmt"

/*
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示：n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：
输入：n = 0
输出：0


提示：
0 <= n <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/*
思路1：暴力计算
	暴力计算出阶乘的值，然后数后缀中0的个数；
	0 <= n <= 10000，那么阶乘的结果该用什么类型存放？int64肯定是不够的
	暴力法看似轻描淡写，其实困难非常，首先要解决的是数据的存储问题。

思路2：数学规律法
	尾数中有几个0，本质就是这些数中间有多少个10，10的质因数是2和5
	所以就是问一组阶乘的质因数里面有多少个2和5的组合
	偶数都有质因数2，所以有一半的数含有2；每5个数才有一个5，所以求2和5的组合，其实就是求有多少个质因数5
		每个5的倍数含有一个5
		每个含5的2次方多提供一个5
		每个含5的3次方再多提供一个5
		……
		直到 n < 5的m次方

		自然数	    5 	10 	15 	20 	25(5*5) 30 	35 	40 	45 	50	……	125(5*5*5)	……	n-n%5
		含5的1次方	1 	1  	1  	1  	1		1	1	1	1	1	……	1			……	1
		含5的2次方					1						1		1
		含5的3次方													1

	所以就是计算： n/5 + n/(5^2) + n/(5^3) +……+ n/(5^m) 直到 n<(5^m)

todo 由于go没有内置指数计算方法，所以自己封装了一个，但后来一想，不就是循环因子每次乘5嘛，就改进了一次……编程之道，循序渐进

*/

// 第一版
func trailingZeroes1(n int) int {
	exponent := func(a, n int) int { // 计算指数的函数
		result := 1
		for i := n; i > 0; i >>= 1 {
			if i&1 != 0 {
				result *= a
			}
			a *= a
		}
		return result
	}

	target := 0

	for i, tmp := 1, exponent(5, 1); n >= tmp; i++ {
		target += n / exponent(5, i)
		tmp = exponent(5, i+1)
	}
	return target
}

// 第二版
func trailingZeroes2(n int) int {
	target := 0
	for tmp := 5; n >= tmp; tmp *= 5 {
		target += n / tmp
	}
	return target
}

// 第三版
func trailingZeroes(n int) (ans int) {
	for n > 0 {
		n /= 5
		ans += n
	}
	return
}

func main() {
	test1()
	test2()
	test3()
	test4()
	test5()
}

// 输入：n = 3  输出：0
func test1() {
	fmt.Println(0 == trailingZeroes(3))
}

// 输入：n = 5  输出：1
func test2() {
	fmt.Println(1 == trailingZeroes(5))
}

// 输入：n = 0  输出：0
func test3() {
	fmt.Println(0 == trailingZeroes(0))
}

// 输入：n = 50  输出：12
func test4() {
	fmt.Println(12 == trailingZeroes(50))
}

// 输入：n = 250  输出：62
func test5() {
	fmt.Println(62 == trailingZeroes(250))
}
